#pragma once

#include "type.h"
#include "plane.h"

namespace ChunkSystem
{
	/**
	*	This class is the contents of a convex hull. Pointers to it
	*	are stored in a HullTree, and are returned back from some routines.
	*
	*	@see HullTree
	*/
	class HullContents
	{
	public:
		HullContents() : pNext_( NULL ) {}
		virtual ~HullContents() {}

		mutable const HullContents * pNext_;
	};

	typedef std::vector< const HullContents * >	HullContentsSet;


	/**
	*	This class is the border of a convex hull. It is simply a vector
	*	of plane equations.
	*
	*	@see HullTree
	*/
	typedef std::vector< Common::Plane > HullBorder;

	typedef std::vector< Common::Vector2 > Portal2D;

	/**
	*	This class is a tree of convex hulls. The hull is defined by the
	*	planes that make it up, and a (user-derived) HullContents object.
	*/
	class HullTree
	{
	public:

		class Portal3D
		{
		public:
			Portal3D() { }
			Portal3D( const Common::Plane& plane, Portal2D& portal );

			typedef std::vector<Common::Vector3> V3Vector;
			V3Vector& points()		{ return points_; }

		private:
			V3Vector	points_;
		};

		typedef std::vector< Portal3D > HullOutLines;
		typedef HullOutLines::iterator itrHullOutLines;

		HullTree();
		~HullTree();

		void Add( const HullBorder& border, const HullContents* tag, HullOutLines* pOutLine = NULL );

		const HullContents* TestPoint( const Common::Vector3& point ) const;

		//void print( int depth, bool back ) const;
		//long size( int depth, bool back ) const;

		/**
		*	This class implements the traversal of a hulltrees contents.
		*/
		class Traversal
		{
		public:
			const HullContents* next();

		private:
			Traversal( const HullTree* pTree, const Common::Vector3& source, const Common::Vector3 & extent, float radius ) :
			delta_( extent - source ),
				source_( source ),
				pPull_( NULL ),	// pullAt not initialised
				radius_( radius ),
				zeroRadius_( radius == 0.f )
			{
				stack_.clear();
				stack_.push_back( StackElt( pTree, -1, 0, 1 ) );
			}

			Common::Vector3	delta_;
			const Common::Vector3& source_;

			const HullContentsSet* pPull_;
			unsigned int	pullAt_;

			float			radius_;
			bool			zeroRadius_;

			struct StackElt
			{
				StackElt( const HullTree* pNode, int eBack, float st, float et ) :
			pNode_( pNode ), eBack_( eBack ), st_( st ), et_( et ) {}

			const HullTree *	pNode_;
			int					eBack_;
			float				st_;
			float				et_;
			};
			//static VectorNoDestructor< StackElt >	stack_;
			std::vector<StackElt> stack_;
				 
			friend class HullTree;
		};

		friend class Traversal;

		Traversal traverse( const Common::Vector3& source, const Common::Vector3& extent, float radius = 0.f ) const
		{
			return Traversal( this, source, extent, radius );
		}

	private:
		HullTree( const Common::Plane& plane, HullTree*& firstMarked );

		void AddPlane( const Common::Plane& plane, Portal3D& outline, HullTree*& firstMarked );

		Common::Plane		divider_;

		HullTree*			pFront_;
		HullTree*			pBack_;

		HullContentsSet		tagFront_;
		HullContentsSet		tagBack_;

		int					marked_;
		HullTree*			pNextMarked_;

		// values for marked_:
		// 0 => none, & 1 => back, & 2 => front
		// & 256 => not back, & 512 => not front
		// & 65536 => new (in this hull)
	};

}
